package org.chengn.level_middle.context2707;

/**
 * @Title: Context2707
 * @Author ChengN
 * @Package org.chengn.level_middle.context2707
 * @Date 2024/1/9 1:18
 * @description: 字符串中的额外字符
 */
public class Context2707 {
    public int minExtraChar(String s, String[] dictionary) {
        int[] dp = new int[s.length() + 1];
        for (int i = 0; i <= s.length(); ++i)
            dp[i] = i;
        for (int i = 1; i <= s.length(); ++i) {
            dp[i] = Math.min(dp[i], dp[i - 1] + 1);
            for (String item : dictionary) {
                if (check(i, s, item)) {
                    dp[i] = Math.min(dp[i - item.length()], dp[i]);
                }
            }
        }
        return dp[s.length()];
    }


    boolean check(int idx, String s, String item) {
        if (idx < item.length())
            return false;

        for (int i = 0; i < item.length(); ++i) {
            if (s.charAt(idx - item.length() + i) != item.charAt(i)) return false;
        }

        return true;
    }
}
